import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().wordBreak("leetcode", Arrays.asList("leet", "code")));
        System.out.println(new Solution().wordBreak("applepenapple", Arrays.asList("apple", "pen")));
        System.out.println(new Solution().wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")));
    }
}


class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        StringBuilder sb = new StringBuilder();
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                int left = i - word.length();

                if (left < 0) {
                    continue;
                }

                if (dp[left] && isequal(s, left, i, word)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    boolean isequal(String s, int start, int end, String target) {
        if (end - start != target.length()) {
            return false;
        }
        for (int i = 0; i < target.length(); i++) {
            if (s.charAt(start + i) != target.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}